package com.dkd.day20250619;

public class SolutionfindKth {
    public static void main(String[] args) {

    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param a int整型一维数组
     * @param n int整型
     * @param K int整型
     * @return int整型
     */
    //我恨递归
    public int findKth (int[] a, int n, int K) {
        // write code here
        return findK(a, 0, n-1, K);
    }


    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[left]; // 选择最左边的元素作为基准值（pivot）

        while (left < right) {
            // 从右向左扫描，找到第一个大于 pivot 的元素
            while (left < right && arr[right] <= pivot) {
                right--;
            }
            arr[left] = arr[right]; // 将该元素移到左边

            // 从左向右扫描，找到第一个小于 pivot 的元素
            while (left < right && arr[left] >= pivot) {
                left++;
            }
            arr[right] = arr[left]; // 将该元素移到右边
        }
        arr[left] = pivot; // 将基准值放到最终位置
        return left; // 返回基准值的索引
    }

    public static int findK(int[] arr, int left, int right, int k) {
        if (left <= right) {
            int pivot = partition(arr, left, right); // 对当前区间进行分区

            if (pivot == k - 1) {
                return arr[pivot]; // 如果基准值的位置正好是第 K 大的位置，直接返回
            } else if (pivot < k - 1) {
                return findK(arr, pivot + 1, right,
                        k); // 第 K 大在右半部分，递归搜索右半部分
            } else {
                return findK(arr, left, pivot - 1,
                        k); // 第 K 大在左半部分，递归搜索左半部分
            }
        }
        return -1; // 如果区间无效（left > right），返回 -1（题目可能保证 k 有效，此情况不会发生）
    }
}
